﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Bio7
{
    public class SbhNegative
    {
        private List<int> TopologicalSort(List<List<int>> V)
        {
            var used = new List<int>();
            var visited = new List<int>();

            for (int i = 0; i < V.Count; i++)
            {
                visited.Add(0);
            }
            for (int i = 0; i < V.Count; i++)
            {
                if (visited[i] == 0)
                {
                    this.Dfs(i, V, visited, used);
                }
            }

            return used;
        }

        private List<List<int>> StronglyConnectedComponents(List<List<int>> V)
        {
            var n = V.Count;
            var result = new List<List<int>>();
            var S = new List<int>();
            var visited = new List<int>();

            for (int i = 0; i < n; i++)
            {
                visited.Add(0);
            }

            for (int i = 0; i < n; i++)
            {
                if (visited[i] == 0)
                {
                    this.Dfs(i, V, visited, S);
                }
            }

            List<List<int>> T = this.Transpose(V);
            visited = new List<int>();

            for (int i = 0; i < n; i++)
            {
                visited.Add(0);
            }
            for (int i = n - 1; i >= 0; i--)
            {
                int u = S[i];
                if (visited[u] == 0)
                {
                    var used = new List<int>();
                    this.Dfs(u, T, visited, used);
                    result.Add(used);
                }
            }
            return result;
        }

        private void Dfs(int u, List<List<int>> V, List<int> visited, List<int> s)
        {
            visited[u] = 1;
            for (int i = 0; i < V[u].Count; i++)
            {
                if (visited[V[u][i]] == 0)
                {
                    this.Dfs(V[u][i], V, visited, s);
                }
            }

            s.Add(u);
        }

        private List<List<int>> Transpose(List<List<int>> V)
        {
            var T = new List<List<int>>();
            for (var i = 0; i < V.Count; i++)
            {
                T.Add(new List<int>());
            }

            for (var i = 0; i < V.Count; i++)
            {
                for (var j = 0; j < V[i].Count; j++)
                {
                    T[V[i][j]].Add(i);
                }
            }
            return T;
        }

        public List<List<int>> CreateAdjacencyMatrix(Instance instance, int min_level)
        {
            min_level = 16384;
            var oligs = instance.Oligs;
            var n = instance.Oligs.Count;

            var adjacency_matrix = new List<List<int>>(n);

            for (var i = 0; i < adjacency_matrix.Count; i++)
            {
                adjacency_matrix[i] = new List<int>(n);
            }

            for (var i = 0; i < n; i++)
            {
                for (var j = 0; j < n; j++)
                {
                    adjacency_matrix[i][j] = oligs[i].Distance(oligs[j]);
                    if (i == j)
                    {
                        adjacency_matrix[i][j] = min_level + 1;
                    }
                    if (adjacency_matrix[i][j] < min_level)
                    {
                        min_level = adjacency_matrix[i][j];
                    }
                }
            }
            return adjacency_matrix;
        }

        public List<List<int>> CreateAdjacencyMatrixRelative(Instance instance, out int max_level)
        {
            max_level = 0;
            var oligs = instance.Oligs;
            var n = instance.Oligs.Count;

            var adjacency_matrix = new List<List<int>>();
            for (var i = 0; i < n; i++)
            {
                adjacency_matrix.Add(new List<int>());
            }

            for (var i = 0; i < n; i++)
            {
                for (var j = 0; j < n; j++)
                {
                    var temp = adjacency_matrix[i];

                    temp.Add(oligs[i].Sequence.Length - oligs[i].Distance(oligs[j]));
                    if (i == j)
                    {
                        temp[j] = max_level - 1;
                    }
                    if (temp[j] > max_level)
                    {
                        max_level = adjacency_matrix[i][j];
                    }

                    adjacency_matrix[i] = temp;
                }
            }
            return adjacency_matrix;
        }

        public List<List<int>> CreateAdjacencyList(List<List<int>> adjacency_matrix, int edge_level)
        {
            var n = adjacency_matrix.Count;
            var V = new List<List<int>>();
            for (var i = 0; i < n; i++)
            {
                V.Add(new List<int>());
            }

            for (var i = 0; i < n; i++)
            {
                for (var j = 0; j < n; j++)
                {
                    if (adjacency_matrix[i][j] == edge_level && i != j)
                    {
                        V[i].Add(j);
                    }
                }
            }
            return V;
        }

        private void PrintGraphInDotFormat(List<List<int>> V)
        {
            Console.WriteLine("digraph G{");
            for (int i = 0; i < V.Count; i++)
            {
                for (int j = 0; j < V[i].Count; j++)
                {
                    Console.WriteLine("{0} -> {1}", i, V[i][j]);
                }
            }
            Console.WriteLine("}\n");
        }

        private List<int> SimpleCalc(List<List<int>> V)
        {
            var sorted = this.TopologicalSort(V);
            var distance = Enumerable.Repeat(-1, sorted.Count).ToList();
            int u;
            for (int i = 0; i < sorted.Count; i++)
            {
                u = sorted[i];
                distance[u] = 0;
                int v;
                for (var j = 0; j < V[u].Count; j++)
                {
                    v = V[u][j];
                    distance[u] = Math.Max(distance[u], distance[v] + 1);
                }
            }

            var solution = new List<int>();
            u = distance.IndexOf(distance.Max());
            solution.Add(u);

            while (distance[u] != 0)
            {
                int v = 0;
                for (int i = 0; i < V[u].Count; i++)
                {
                    if (distance[u] == distance[V[u][i]] + 1)
                    {
                        v = V[u][i];
                        break;
                    }
                }
                u = v;
                solution.Add(u);
            }
            return solution;
        }

        public List<int> Calc(List<List<int>> V)
        {
            while (this.RemoveEdge(V))
            {
            }
            return this.SimpleCalc(V);
        }

        private bool RemoveEdge(List<List<int>> V)
        {
            var scc = this.StronglyConnectedComponents(V);

            var sccNumber = Enumerable.Repeat(0, V.Count).ToList();
            for (int i = 0; i < scc.Count; i++)
            {
                for (int j = 0; j < scc[i].Count; j++)
                {
                    sccNumber[scc[i][j]] = i;
                }
            }

            var SCC = new List<List<int>>();
            for (var i = 0; i < scc.Count; i++)
            {
                SCC.Add(new List<int>());
            }
            for (var i = 0; i < V.Count; i++)
            {
                for (var j = 0; j < V[i].Count; j++)
                {
                    if (sccNumber[i] != sccNumber[V[i][j]])
                    {
                        SCC[sccNumber[i]].Add(sccNumber[V[i][j]]);
                    }
                }
            }
            var sorted = this.TopologicalSort(SCC);
            var distance = Enumerable.Repeat(0, V.Count).ToList();

            for (var i = 0; i < sorted.Count; i++)
            {
                int s = sorted[i];
                for (var k = 0; k < scc[s].Count; k++)
                {
                    int u = scc[s][k];
                    distance[u] = 0;
                    for (int j = 0; j < V[u].Count; j++)
                    {
                        int v = V[u][j];
                        if (sccNumber[v] != sccNumber[u])
                        {
                            distance[u] = Math.Max(distance[u], distance[v] + 1);
                        }
                    }
                }
                if (scc[s].Count > 1)
                {
                    var maxI = scc[s][0];
                    for (var k = 0; k < scc[s].Count; k++)
                    {
                        var u = scc[s][k];
                        if (distance[u] > distance[maxI])
                        {
                            maxI = u;
                        }
                    }
                    var tmp = new List<int>();
                    for (var j = 0; j < V[maxI].Count; j++)
                    {
                        if (sccNumber[V[maxI][j]] != sccNumber[maxI])
                        {
                            tmp.Add(V[maxI][j]);
                        }
                    }
                    V[maxI] = tmp;

                    return true;
                }
            }
            return false;
        }
    }
}